package com.zhanghp.class034;

import com.zhanghp.common.ListNode;

/**
 * 每k个节点一组翻转链表<br/>
 * 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
 *
 * @author zhanghp
 * @since 2024/4/10 17:11
 */
public class Code02_ReverseNodesInkGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = teamEnd(head, k);
        if (end == null) {
            return start;
        }
        // 第一组很特殊因为牵扯到换头的问题
        head = end;
        reverse(start, end);
        // 翻转之后start变成了上一组的结尾节点
        ListNode lastTeamEnd = start;
        while (lastTeamEnd.next != null) {
            start = lastTeamEnd.next;
            end = teamEnd(start, k);

            if (end == null) {
                break;
            }
            reverse(start, end);
            // 最后赋值
            lastTeamEnd.next = end;
            lastTeamEnd = start;
        }
        return head;
    }

    // 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
    public ListNode teamEnd(ListNode head, int k) {
        while (--k > 0 && head != null) {
            head = head.next;
        }
        return head;
    }

    // s -> a -> b -> c -> e -> 下一组的开始节点
    // 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
    public void reverse(ListNode s, ListNode e) {
        e = e.next;
        ListNode pre = null, cur = s, next;
        while (cur != e) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        s.next = e;
    }
}
